package algorithm;

import java.lang.reflect.Array;

public class BinarySearch {
    public static int binarySearchBasic(int[] a, int target) {
        int i = 0, j = a.length - 1;
        while (i <= j) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m - 1;
            } else if (a[m] < target) {
                i = m + 1;
            } else {
                return m;
            }
        }
        return -1;
    }

    public static int binarySearchAlternative(int[] a, int target) {
        int i = 0, j = a.length; // first modification
        while (i < j) { // second modification
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m; // third modification
            } else if (a[m] < target) {
                i = m + 1;
            } else {
                return m;
            }
        }
        return -1;
    }

    public static int binarySearchBalance(int[] a, int target) {
        int i = 0, j = a.length;
        while (j - i > 1) {
            int m = (i + j) >>> 1;
            if (target < a[m]) {
                j = m;
            } else {
                i = m;
            }
        }
        if (a[i] == target) {
            return i;
        }
        return -1;
    }

    public static int binarySearchLeftMost(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        int candidate = -1;
        while (low <= high) {
            int mid = (low + high) >>> 1;
            int midVal = arr[mid];
            if (target < midVal) {
                high = mid - 1;
            } else if (midVal < target) {
                low = mid + 1;
            } else {
                candidate = mid;
                high = mid - 1;
            }
        }
        return candidate;
    }
}
